import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution749 {

    int[] dx=new int[]{1,0,-1,0};
    int[] dy=new int[]{0,1,0,-1};
    int count=0;

    public int containVirus(int[][] isInfected) {
        int ans=0;
        while (true){
            boolean[][] visit=new boolean[isInfected.length][isInfected[0].length];
            List<Set<int[]>> region=new ArrayList<>();
            List<Integer> c=new ArrayList<>();
            for (int i=0;i<isInfected.length;i++){
                for (int j=0;j<isInfected[0].length;j++){
                    if (isInfected[i][j]==1  && !visit[i][j]){
                        count=0;
                        Set<int[]> set=new HashSet<>();
                        dfs(i,j,isInfected,set,visit);
                        c.add(count);
                        region.add(set);
                        for (int k=0;k<isInfected.length;k++){
                            for (int l=0;l<isInfected[0].length;l++){
                                if (isInfected[k][l]==0){
                                    visit[k][l]=false;
                                }
                            }
                        }
                    }
                }
            }
            if (region.isEmpty()){
                break;
            }
            int max=-1,pos=-1;
            for (int i=0;i<region.size();i++){
                if (c.get(i)>max){
                    max=c.get(i);
                    pos=i;
                }
            }
            Set<int[]> set=region.get(pos);
            for (int[] ints : set) {
                for (int i=0;i<4;i++){
                    int x=ints[0]+dx[i];
                    int y=ints[1]+dy[i];
                    if (x>=0 && x<isInfected.length && y>=0 && y<isInfected[0].length){
                        if (isInfected[x][y]==0){
                            ans++;
                        }
                    }
                }
            }
            for (int[] ints : set) {
                isInfected[ints[0]][ints[1]]=2;
            }
            for (int i=0;i<region.size();i++){
                if (pos!=i){
                    Set<int[]> set1=region.get(i);
                    for (int[] ints : set1) {
                        for (int j=0;j<4;j++){
                            int x=ints[0]+dx[j];
                            int y=ints[1]+dy[j];
                            if (x>=0 && x<isInfected.length && y>=0 && y<isInfected[0].length){
                                if (isInfected[x][y]==0){
                                    isInfected[x][y]=1;
                                }
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }

    private void dfs(int x, int y, int[][] map, Set<int[]> set, boolean[][] visit) {
        if (!(x>=0 && x<map.length && y>=0 && y<map[0].length) || visit[x][y]){
            return;
        }
        visit[x][y]=true;
        if (map[x][y]==0){
            count++;
            return;
        }else if (map[x][y]==1) {
            set.add(new int[]{x, y});
        }else {
            return;
        }
        for (int i=0;i<4;i++){
            dfs(x+dx[i],y+dy[i],map,set,visit);
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution749().containVirus(new int[][]{{0,0,1,1,1,0,1,0,0,0},{1,1,1,0,0,0,1,1,0,1},{0,0,0,0,0,0,1,0,0,0},{0,0,0,0,1,0,1,0,0,0},{1,0,0,0,1,1,1,0,0,0},{0,0,0,1,0,1,1,0,0,0},{1,0,0,0,0,1,0,0,0,1},{1,0,0,0,0,0,0,0,0,1},{0,1,0,0,0,0,0,0,1,0},{1,1,0,0,0,1,0,1,0,0}}));
    }
}
